package com.mlh.heap;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/9/4 17:01
 * @DESCRIPTION
 */
public class Heap {
    //将新插入元素放在数组的最后面，让它上浮
    public void insert(int[]tree,int end){
        if(end>=tree.length){
            return;
        }
        //该节点的父节点索引
        int fatherIndex=(end-1)/2;
        while(fatherIndex>=0){
            if(tree[fatherIndex]<tree[end]){
                //交换两者位置
                swap(tree,fatherIndex,end);
                end=fatherIndex;
                fatherIndex=(end-1)/2;
            }else{
                break;
            }
        }
    }

    public void swap(int[]tree,int a,int b){
        tree[a]=tree[a]^tree[b];
        tree[b]=tree[a]^tree[b];
        tree[a]=tree[a]^tree[b];
    }

    //将初始数组堆化
    public void heapify(int[]tree){
        for (int i = 1; i < tree.length; i++) {
            insert(tree,i);
        }
    }

    //返回堆顶值 然后将数组最后一个元素换到堆顶，开始下沉操作
    public int getMax(int[]tree,int end){
        int res=tree[0];
        tree[0]=tree[end];
        //开始下沉
        int index=0;
        int left=(index+1)*2-1;
        int right=(index+1)*2;
        while(left<end){
            if(right<end){//有右子节点
                int maxChildIndex=tree[left]>tree[right]?left:right;
                if(tree[maxChildIndex]>tree[index]){
                    swap(tree,maxChildIndex,index);
                    index=maxChildIndex;
                    left=(index+1)*2-1;
                    right=(index+1)*2;
                }else{
                    break;
                }
            }else{//没有右子节点
                if(tree[left]>tree[index]){
                    swap(tree,left,index);
                    index=left;
                    left=(index+1)*2-1;
                }else{
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        // Heap heap=new Heap();
        // int[]tree=new int[]{111,2,13,24,25,63,74,8,95};
        // heap.heapify(tree);
        // System.out.println(Arrays.toString(tree));
        // for (int i = 0; i < tree.length; i++) {
        //     System.out.println(heap.getMax(tree,tree.length-1-i));
        // }
        int[]tree=new int[]{111,2,13,24,25,63,74,8,95};
        HeapPractice heap = new HeapPractice(tree);
        heap.insert(99999);
        heap.insert(999991);
        int len=heap.size;
        for (int i = 0; i <=len; i++) {
            System.out.println(heap.getMin());
        }
    }
}

class HeapPractice{
    int[]tree;
    int size=-1;//最后一个元素的下标，数组中没元素下标为-1
    public HeapPractice(int[]tree){
        this.tree= tree;
        this.heapify();
    }

    private void heapify() {
        for (int i = 0; i < tree.length; i++) {
            insert(tree[i]);
        }
    }

    public  void insert(int val) {
        ++size;
        if(size>tree.length-1){//超过了就进行扩容
            int[]temp=new int[size*2];//两倍扩容
            System.arraycopy(tree,0,temp,0,tree.length);//将元素组进行拷贝
            tree=temp;
        }
       // 将新增的值放在数组的最后
       tree[size]=val;
       //开始上浮
        int child=size;
        int root=(child-1)/2;
        while(root>=0){
            if(tree[root]>tree[child]){
                swap(root,child);
                child=root;
                root=(child-1)/2;
            }else{
                break;
            }
        }
    }

    private void swap(int a, int b) {
        int temp=tree[a];
        tree[a]=tree[b];
        tree[b]=temp;
    }

    public int getMin(){
        int res=tree[0];
        tree[0]=tree[size];
        --size;
        //开始下沉
        int root=0;
        int left=(root+1)*2-1;
        int right=(root+1)*2;
        while(left<=size){
            if(right<=size){
                int min = Math.min(tree[left], tree[right]);
                int minIndex=tree[left]>tree[right]?right:left;
                if(min<tree[root]){
                    swap(root,minIndex);
                    root=minIndex;
                }else{
                    break;
                }
            }else{
                if(tree[root]>tree[left]){
                    swap(root,left);
                    root=left;
                }else{
                    break;
                }
            }
            left=(root+1)*2-1;
            right=(root+1)*2;
        }
        return res;
    }
}
